package q221_maximalSquare;

public class Solution {
    /*
    使用动态规划的方式来解决该问题
    我们考虑dp[i][j]代表该位置为右下角时，此时能够构成的最大正方形的边长
    首先考虑当该位置为0时，边长只能是0
    然后考虑在i = 0或者j = 0时，即使该位置是1，边长也只能是1
    其他情况时，边长应该从三个位置推算过来
    也就是Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1])
    要从这三者中选取最小值来推算当前位置的最长边长
    最后每次遇到一个1的格子就更新一次maxS
    即可得到能够拼出的最大正方形
     */
    public int maximalSquare(char[][] matrix) {
        int maxS = 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == '1') {
                    if (i * j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }

                    maxS = Math.max(dp[i][j] * dp[i][j], maxS);
                }
            }
        }

        return maxS;
    }
}
